package com.ruoyi.learn.java.algorithm.recursionDivideandConquer;

import java.util.Arrays;

/**
 * 实例 1: 归并排序 (Merge Sort)
 * 归并排序是分治法最经典的体现。
 *
 * 问题: 对一个数组进行排序。
 * 分解: 将数组从中间分成两个大小近似相等的子数组。
 * 解决: 递归地对左半部分和右半部分进行归并排序。
 * 合并: 将两个已经排好序的子数组合并成一个有序的数组（通过双指针比较）。
 */
public class MergeSort {

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) { // 基本情况：当 left >= right 时，子数组只有一个或零个元素，已有序
            // 1. 分解
            int mid = left + (right - left) / 2; // 防止整数溢出

            // 2. 解决
            mergeSort(arr, left, mid);     // 排序左半部分
            mergeSort(arr, mid + 1, right); // 排序右半部分

            // 3. 合并
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        // 创建临时数组存储合并结果
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        // 比较两个子数组的元素，将较小的放入 temp
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 将剩余元素复制到 temp
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        // 将 temp 中的元素复制回原数组
        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10,1,111,11,333,3,33};
        System.out.println("Original: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("Sorted: " + Arrays.toString(arr));
    }
}
